package com.peng.linkedlist;

/**
 * K个节点的组内逆序调整问题：
 * 给定一个单链表的头节点head，和一个正数k
 * 实现k个节点的小组内部逆序，如果最后一组不够k个就不调整
 * 例子: （假设K=3）
 * 调整前：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8，k = 3
 * 调整后：3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8
 */
public class Test05_ReverseNodesInKGroup {

    public static Node reverseNodesInKGroup(Node head,int K){
        if(head==null){
            return null;
        }

        Node start = head;
        Node end = getKGroupEndNode(start, K);
        if(end==null){
            return head;
        }
        reverseNode(start,end);

        //记录每一次的尾巴，为了后面去链接下一个的头
        Node lastEnd = start;
        head = end;

        while (lastEnd.next!=null){
            start = lastEnd.next;
            end = getKGroupEndNode(start, K);
            if(end==null){
                return head;
            }
            reverseNode(start,end);
            lastEnd.next = end;
            lastEnd = start;
        }

        return head;



    }

    private static void reverseNode(Node start, Node end) {
       end = end.next;
       Node next;
       Node cur = start;
       Node pre = null;
       while (cur!=end){
           next = cur.next;
           cur.next = pre;
           pre =cur;
           cur = next;
       }
       start.next = end;
    }

    public static Node getKGroupEndNode(Node start,int K){
        while (--K!=0 && start!=null){
            start = start.next;
        }
        return start;
    }

    public static void main(String[] args) {
        Node node = LinkedListUtils.makeLinkedList(8);
        Node head = reverseNodesInKGroup(node, 3);
        LinkedListUtils.printNodes(head);
    }
}
